#include <iostream>

class Solution
{
  public:
    bool check(int x, int y)
    {
        if (x > 4 || x < 0)
            return false;
        if (y > 3 || y < 0)
            return false;
        return table[x][y] != '*' && table[x][y] != '#';
    }

    void init()
    {
        for (int x = 0; x < 4; x++)
        {
            for (int y = 0; y < 3; y++)
            {
                if (table[x][y] == '*' || table[x][y] == '#')
                    continue;
                canJump[x][y] = 0;
                for (int i = 0; i < 8; i++)
                {
                    for (int j = 0; j < 8; j++)
                    {
                        int tx = x + dx[i];
                        int ty = y + dy[i];
                        if (check(tx, ty))
                        {
                            canJump[x][y]++;
                        }
                    }
                }
            }
        }
    }

    long long f(int x, int y, int len)
    {
        if (len == this->n)
        {
            return 1;
        }
        if (table[x][y] == '*' || table[x][y] == '#') {
            return 0;
        }
        long long ans = 0;
        for (int i = 0; i < 8; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (check(tx, ty))
            {
                // TODO: 问题是怎么与已经初始化的结果数组结合
                ans += f(tx, ty, len + 1);
            }
        }
        return ans;
    }

    int solve()
    {
        long long ans = 0;
        for (int x = 0; x < 4; x++)
        {
            for (int y = 0; y < 3; y++)
            {
                ans = (ans + f(x, y, 0)) % MOD;
            }
        }
        return static_cast<int>( ans );
    }

    int knightDialer(int n)
    { // 长度为n的号码
        init();
        return solve();
    }

  private:
    int MOD = static_cast<int>(10e9 + 7);
    int maxLen = 5010;
    int n;
    int dx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
    char table[4][3] = {
        {'1', '2', '3'},
        {'4', '5', '6'},
        {'7', '8', '9'},
        {'*', '0', '#'}};
    int canJump[4][3] = {0};
};

int main()
{
    Solution s;
    std::cout << s.knightDialer(2) << std::endl;
}